package zcw.com.lib_leet_code;

import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2022/2/23.<br><br>
 *
 * 中等：排序数组
 */
public class Topic912 {

    public static void main(String[] args) {
        BaseSolution solution = new SolutionQuick();

        int[] array = new int[] {5,2,3,1};
        Util.printArray(solution.sortArray(array));

        array = new int[] {5,1,1,2,0,0};
        Util.printArray(solution.sortArray(array));

        // 计算超长数组排序时间
        String basePath = System.getProperties().getProperty("user.dir");
        array = Util.readArrayFromFile(basePath + "/lib_leet_code/IntArray");

        solution = new SolutionSelect();
        BaseSolution proxy = (BaseSolution) Util.calculateTime("选择排序", solution);
        proxy.sortArray(array);

        solution = new SolutionBubble();
        proxy = (BaseSolution) Util.calculateTime("冒泡排序", solution);
        proxy.sortArray(array);

        solution = new SolutionInsert();
        proxy = (BaseSolution) Util.calculateTime("插入排序", solution);
        proxy.sortArray(array);

        solution = new SolutionQuick();
        proxy = (BaseSolution) Util.calculateTime("快速排序", solution);
        proxy.sortArray(array);
    }

    protected interface BaseSolution {
        int[] sortArray(int[] nums);
    }

    /**
     * 插入排序
     */
    private static class SolutionInsert implements BaseSolution {

        @Override
        public int[] sortArray(int[] nums) {
            for(int i = 0; i < nums.length - 1; i++) {
                int j = i + 1;
                int temp = nums[j];

                while (j > 0 && nums[j - 1] > temp) {
                    nums[j] = nums[j - 1];
                    j--;
                }

                nums[j] = temp;
            }
            return nums;
        }
    }

    /**
     * 冒泡排序（超时）
     */
    private static class SolutionBubble implements BaseSolution {

        @Override
        public int[] sortArray(int[] nums) {
            for(int i = 0; i < nums.length; i++) {
                for(int j = 0; j < nums.length - i - 1; j++) {
                    if(nums[j] > nums[j + 1]) {
                        int temp = nums[j];
                        nums[j] = nums[j + 1];
                        nums[j + 1] = temp;
                    }
                }
            }
            return nums;
        }
    }

    /**
     * 选择排序
     */
    private static class SolutionSelect implements BaseSolution {

        @Override
        public int[] sortArray(int[] nums) {
            for(int i = 0; i < nums.length; i++) {
                int minIndex = i;
                for(int j = i + 1; j < nums.length; j++) {
                    if(nums[j] < nums[minIndex]) {
                        minIndex = j;
                    }
                }

                int temp = nums[minIndex];
                nums[minIndex] = nums[i];
                nums[i] = temp;
            }
            return nums;
        }
    }

    /**
     * 快排
     */
    private static class SolutionQuick implements BaseSolution {

        @Override
        public int[] sortArray(int[] nums) {
            helper(nums, 0, nums.length - 1);
            return nums;
        }

        private void helper(int[] nums, int start, int end) {
            if(start >= end) {
                return ;
            }

            int left = start;
            int right = end;
            int temp = nums[left];
            while (left < right) {
                while (left < right && nums[right] >= temp) {
                    right--;
                }
                nums[left] = nums[right];

                while (left < right && nums[left] <= temp) {
                    left++;
                }
                nums[right] = nums[left];
            }
            nums[left] = temp;

            helper(nums, start, left - 1);
            helper(nums, left + 1, end);
        }
    }
}
